#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "utilis.hh"


void Swap(int & i, int & j) // hace le swap si i>j
{
	if (i>j)
	{
		int aux = i;
		i=j;
		j = aux;
	}
}

void DecreaseMatrix(int ** M, int i, int j)
{
	if (i>j)
	{
		int aux = i;
		i=j;
		j = aux;
	}
	M[i][j]--;
}

void SetMatrix(int ** M, int i, int j, int k)
{
	if (i>j)
	{
		int aux = i;
		i=j;
		j = aux;
	}
	M[i][j] = k;
}


int GetMatrix(int ** M, int i, int j)
{
	if (i>j)
	{
		int aux = i;
		i=j;
		j = aux;
	}
	return M[i][j];
}

int Random(int i , int j)
{
	return rand() % (j-i) + i;
};

int Random(int i)
{
	return rand() % i;
};

Path * SelectRandom(list<Path*> * L)
{
	if (L->size()<=0) return NULL;

	int index = Random(L->size());

	list<Path*>::iterator it = L->begin();
	advance(it, index);

	Path * elem = *it;
	L->erase(it);

	return elem;
};

int SelectRandom(list<int> * L)
{
	if (L->size()<=0) return -1;

	int index = Random(L->size());

	list<int>::iterator it = L->begin();
	advance(it, index);

	int elem = *it;
	L->erase(it);

	return elem;
};

Path * Random(list<Path*> * L)
{
	if (L->size()<=0) return NULL;

	int index = Random(L->size());

	list<Path*>::iterator it = L->begin();
	advance(it, index);

	return *it;
};

pair<int,int>* SelectRandom(list<pair<int,int>*> * L)
{
	if (L->size()<=0) return NULL;

	int index = Random(L->size());

	list<pair<int,int>*>::iterator it = L->begin();
	advance(it, index);

	pair<int,int>* elem = *it;
	L->erase(it);

	return elem;
};

pair<int, int> * RandomEdge(Path * p) {

	if (p->Size()<=0) return NULL;

	int index = Random(p->Size()-1);

	list<int>::iterator it = p->path->begin();
	advance(it, index);

	pair<int,int>* elem = new pair<int,int>();
	elem->first = *it;
	it++;
	elem->second = *it;

	return elem;
}

int RandomNode(Path * p) {

	if (p->Size()<=0) return -1;

	int index = Random(p->Size());

	list<int>::iterator it = p->path->begin();
	advance(it, index);

	return *it;
}

int Contains(list<int>* l, int elem) {

	for (list<int>::iterator it = l->begin(); it != l->end(); it++)
		if ((*it) == elem) {
			return 1;
		}
	return 0;
}

void DeleteListPath(list<Path*>*& Lp)
{
	if(Lp) {
		for (list<Path*>::iterator it=Lp->begin(); it != Lp->end(); ++it)
			delete *it;
		Lp->clear();
		delete Lp;
		Lp = NULL;
	}
};

void DeleteListPairInt(list<pair<int,int>*> *& list_pair)
{
	if(list_pair) {
		for (list<pair<int,int>*>::iterator it=list_pair->begin(); it != list_pair->end(); ++it)
			delete *it;
		list_pair->clear();
		delete list_pair;
		list_pair = NULL;
	}
};

void DeleteListInt(list<int> *& l)
{
	if(l) {
		l->clear();
		delete l;
		l = NULL;
	}
}

void DeleteMatrix(int **& M, int size)
{
	if(M) {
		for(int i=0; i<size; i++)
			delete[] M[i];

		delete[] M;
		M = NULL;
	}
};

void DeletePair(pair<Graph*, PathMatrix*> *& elem) {
	if(elem) {
		delete elem->first;
		delete elem->second;

		delete elem;
		elem = NULL;
	}
}

void CleanLp(list<Path*>* Lp)
{
	if(Lp) {
		for (list<Path*>::iterator it=Lp->begin(); it != Lp->end(); ++it)
			delete *it;
		Lp->clear();
	}
};

void CleanListPairInt(list<pair<int,int>*> * list_pair)
{
	if(list_pair) {
		for (list<pair<int,int>*>::iterator it=list_pair->begin(); it != list_pair->end(); ++it)
			delete *it;
		list_pair->clear();
	}
};

void CleanListInt(list<int> * l)
{
	if(l) {
		l->clear();
	}
}

void GetSecctionTitle(ifstream & file, Graph * Gp)
{
	string line;
	if(file.good()) getline(file, line);
}

void GetSecctionComment(ifstream & file, Graph * Gp)
{
	string line;
	if(file.good()) getline(file, line);
	if(!line.compare("SECTION Comment"))
	{
		if(file.good()) getline(file, line);
		while(line.compare("END"))
			if(file.good()) getline(file, line);
	}
	else
		cout << "[ERROR][GetSecctionComment]: Invalid format\n";
}

void GetSecctionGraph(ifstream & file, Graph * Gp)
{
	string line;
	int int_value1;
	int int_value2;
	int int_value3;
	int error;

	if(file.good()) getline(file, line);
	if(!line.compare("SECTION Graph"))
	{
		if(file.good()) getline(file, line);
		error = sscanf(line.c_str(),"Nodes %d", &int_value1);
		if(!error || error == EOF) cout << "[ERROR][GetSecctionGraph]: Invalid format" << endl;

		Gp->sizeG = int_value1;

		Gp->_T = new int[Gp->sizeG];
		Gp->W = new int[Gp->sizeG];
		Gp->actived_node = new int[Gp->sizeG];

		Gp->R = new int*[Gp->sizeG];
		Gp->C = new int*[Gp->sizeG];
		Gp->E = new int*[Gp->sizeG];
		for(int i=0; i<Gp->sizeG; i++)
		{
			Gp->C[i] = new int[Gp->sizeG];
			Gp->E[i] = new int[Gp->sizeG];
			Gp->R[i] = new int[Gp->sizeG];
		}

		for(int i=0; i<Gp->sizeG; i++)
		{
			Gp->_T[i] = 0;
			Gp->W[i] = 0;
			Gp->actived_node[i] = 1;

			for(int j=0; j<Gp->sizeG; j++)
			{
				Gp->C[i][j] = 0;
				Gp->E[i][j] = 0;
				Gp->R[i][j] = 0;
			}
		}


		if(file.good()) getline(file, line);
		error = sscanf(line.c_str(),"Edges %d", &int_value1);
		if(!error || error == EOF) cout << "[ERROR][GetSecctionGraph]: Invalid format" << endl;

		if(file.good()) getline(file, line);
		while(line.compare("END"))
		{
			error = sscanf(line.c_str(),"E %d %d %d", &int_value1, &int_value2, &int_value3);
			if(!error || error == EOF) cout << "[ERROR][GetSecctionGraph]: Invalid format" << endl;

			int_value1--;
			int_value2--;

			if(0 > int_value1 || int_value1 >= Gp->sizeG) cout << "[ERROR][GetSecctionGraph]: Invalid terminal " << int_value1+1 << endl;
			if(0 > int_value2 || int_value2 >= Gp->sizeG) cout << "[ERROR][GetSecctionGraph]: Invalid terminal " << int_value1+1 << endl;

			if(int_value1 == int_value2) cout << "[ERROR][GetSecctionGraph]: No admitted edge " << "(" << int_value1+1 << ", " << int_value2 +1<< ")"<< endl;

			SetMatrix(Gp->C, int_value1, int_value2, int_value3);
			SetMatrix(Gp->E, int_value1, int_value2, 1);

			if(file.good()) getline(file, line);
		}
	}
	else
		cout << "[ERROR][GetSecctionGraph]: Invalid format" << endl;
}

void GetSecctionTerminals(ifstream & file, Graph * Gp)
{
	string line;
	int int_value1;
	int error;

	if(file.good()) getline(file, line);
	if(!line.compare("SECTION Terminals"))
	{
		if(file.good()) getline(file, line);
		error = sscanf(line.c_str(),"Terminals %d", &int_value1);
		if(!error || error == EOF) cout << "[ERROR][GetSecctionTerminals]: Invalid format" << endl;

		Gp->T = new list<int>;

		if(file.good()) getline(file, line);
		while(line.compare("END"))
		{
			error = sscanf(line.c_str(),"T %d", &int_value1);
			if(!error || error == EOF) cout << "[ERROR][GetSecctionTerminals]: Invalid format" << endl;

			int_value1--;

			if(0 > int_value1 || int_value1 >= Gp->sizeG) cout << "[ERROR][GetSecctionTerminals]: Invalid terminal " << int_value1+1 << endl;
			Gp->T->push_front(int_value1);
			Gp->_T[int_value1] = 1;

			if(file.good()) getline(file, line);
		}
	}
	else
		cout << "[ERROR][GetSecctionTerminals]: Invalid format" << endl;
}


void GetSecctionRequirementsConnectivity(ifstream & file, Graph * Gp)
{
	string line;
	int int_value1;
	int int_value2;
	int int_value3;
	int error;

	if(file.good()) getline(file, line);
	if(!line.compare("SECTION Requirements Connectivity"))
	{
		if(file.good()) getline(file, line);
		while(line.compare("END"))
		{
			error = sscanf(line.c_str(),"R %d %d %d", &int_value1, &int_value2, &int_value3);
			if(!error || error == EOF) cout << "[ERROR][GetSecctionRequirementsConnectivity]: Invalid format" << endl;

			int_value1--;
			int_value2--;
			if(!Gp->_T[int_value1]) cout << "[ERROR][GetSecctionRequirementsConnectivity]: No is a terminal " << int_value1 << endl;
			if(!Gp->_T[int_value2]) cout << "[ERROR][GetSecctionRequirementsConnectivity]: No is a terminal " << int_value2 << endl;

			SetMatrix(Gp->R, int_value1, int_value2, int_value3);

			//cout << line << "\n";
			if(file.good()) getline(file, line);
		}
	}
	else
		cout << "[ERROR][GetSecctionRequirementsConnectivity]: Invalid format" << endl;
}


void GetSecctionNodeWeight(ifstream & file, Graph * Gp)
{
	string line;
	int int_value1;
	int int_value2;
	int error;

	if(file.good()) getline(file, line);
	if(!line.compare("SECTION Weight Nodes"))
	{
		if(file.good()) getline(file, line);
		while(line.compare("END"))
		{
			error = sscanf(line.c_str(),"W %d %d", &int_value1, &int_value2);
			if(!error || error == EOF) cout << "[ERROR][GetSecctionNodeWeight]: Invalid format" << endl;

			int_value1--;
			Gp->W[int_value1] = int_value2;

			//cout << line << "\n";
			if(file.good()) getline(file, line);
		}
	}
	else
		cout << "[ERROR][GetSecctionNodeWeight]: Invalid format" << endl;
}

void GetSecctionDiameter(ifstream & file, Graph * Gp)
{
	string line;
	int int_value1;
	int error;

	if(file.good()) getline(file, line);
	if(!line.compare("SECTION Diameter"))
	{
		if(file.good()) getline(file, line);
		while(line.compare("END"))
		{
			error = sscanf(line.c_str(),"D %d", &int_value1);
			if(!error || error == EOF) cout << "[ERROR][GetSecctionDiameter]: Invalid format" << endl;
			Gp->diameter = int_value1;

			//cout << line << "\n";
			if(file.good()) getline(file, line);
		}
	}
	else
		cout << "[ERROR][GetSecctionDiameter]: Invalid format" << endl;
}

list<Path*>* ClearCopy(list<Path*> *l) {

	list<Path*>* l_out = new list<Path*>;

	if (l != NULL) {
		for (list<Path*>::iterator it = l->begin(); it != l->end(); it++)
			l_out->push_back(new Path(*it));
	}

	return l_out;
}

void FileToGraph(const char * path, Graph * Gp)
{
	string line;
	ifstream file(path);

	if (file.is_open() && file.good())
	{
		GetSecctionTitle(file, Gp);
		if(file.good()) getline(file, line);

		GetSecctionComment(file, Gp);
		if(file.good()) getline(file, line);

		GetSecctionGraph(file, Gp);
		if(file.good()) getline(file, line);

		GetSecctionTerminals(file, Gp);
		if(file.good()) getline(file, line);

		GetSecctionRequirementsConnectivity(file, Gp);
		if(file.good()) getline(file, line);

		GetSecctionNodeWeight(file, Gp);
		if(file.good()) getline(file, line);

		GetSecctionDiameter(file, Gp);

		Gp->Cost();

		file.close();
	}
	else {
		cout << "[ERROR][FileToGraph]: Unable to open file" << endl;
		exit(1);
	}
}


bool ExistMiiGreaterThanZero(int ** M, int size) {
	for(int i=0; i<size; i++)
		for(int j=i; j<size; j++)
			if (M[i][j]) return true;

	return false;
}


void PrintGraph(Graph * G) {
	cout << "Print Graph ////////////////////////////////////////////////////////////////////////" << endl;

	cout << "Size: " << G->sizeG << endl;

	cout << "Connectivity: "<< endl;
	for(int i=0; i<G->sizeG; i++)
	{
		for(int j=0; j<G->sizeG; j++)
			cout << G->C[i][j] << " ";
		cout << endl;
	}
	cout << endl;

	cout << "Weigth: "<< endl;
	for(int i=0; i<G->sizeG; i++)
	{
		cout << G->W[i] << " ";
	}
	cout << endl;
	cout << endl;

	cout << "Enables edge: "<< endl;
	for(int i=0; i<G->sizeG; i++)
	{
		for(int j=0; j<G->sizeG; j++)
			cout << G->E[i][j] << " ";
		cout << endl;
	}
	cout << endl;

	cout << "Requirements Connectivity: "<< endl;
	for(int i=0; i<G->sizeG; i++)
	{
		for(int j=0; j<G->sizeG; j++)
			cout << G->R[i][j] << " ";
		cout << endl;
	}
	cout << endl;

	cout << "Terminals: "<< endl;
	for (list<int>::iterator it=G->T->begin(); it != G->T->end(); ++it)
		cout << *it+1 << " ";
	cout << endl;

	cout << "Is Terminals: "<< endl;
	for(int i=0; i<G->sizeG; i++)
	{
		cout << G->_T[i] << " ";
	}
	cout << endl;

	cout << "Diameter: " << G->diameter << endl;

	cout << "Active Nodes: "<< endl;
	for(int i=0; i<G->sizeG; i++)
	{
		cout << G->actived_node[i] << " ";
	}
	cout << endl;

	cout << "Cost: " << G->Cost() << endl;


	cout << "Print Graph ////////////////////////////////////////////////////////////////////////" << endl;

};

void PrintPath(Path * p) {
	for (list<int>::iterator it=p->path->begin(); it != p->path->end(); ++it)
		cout << *it+1 << " ";
	cout << endl;
}

void PrintPath(Path *p1, Path *p2) {

	for (list<int>::iterator it=p1->path->begin(); it != p1->path->end(); ++it)
		cout << *it+1 << " ";

	cout << "  :  ";
	for (list<int>::iterator it=p2->path->begin(); it != p2->path->end(); ++it)
			cout << *it+1 << " ";

	cout << endl;
}


void PrintListInt(list<int> * l) {
	for (list<int>::iterator it=l->begin(); it != l->end(); ++it)
		cout << *it+1 << " ";
	cout << endl;
}

void PrintListPath(list<Path *> * Lp) {
	for (list<Path*>::iterator it=Lp->begin(); it != Lp->end(); ++it)
		PrintPath(*it);
}

void PrintListPairInt(list<pair<int,int>*> * l) {
	for (list<pair<int,int>*>::iterator it=l->begin(); it != l->end(); ++it)
		cout << "(" << (*it)->first+1 << ", " << (*it)->second+1 << ")" << " " <<endl;
	cout << endl;
}


void PrintPartialGraph(Graph * G) {

	cout << "Print Graph ////////////////////////////////////////////////////////////////////////" << endl;
	/*cout << "SECTION Nodes" << endl;
	for(int i=0; i<G->sizeG; i++)
		if(G->actived_node[i]) {
			if(G->_T[i])
				cout << "T " << i+1 << endl;
			else
				cout << "O " << i+1 << endl;
		}

	cout << "END" << endl;
	cout << endl;*/

	/*cout << "SECTION Requirements Connectivity: "<< endl;
	for(int i=0; i<G->sizeG; i++)
	{
		for(int j=0; j<G->sizeG; j++)
			cout << G->R[i][j] << " ";
		cout << endl;
	}
	cout << endl;*/


	cout << "SECTION Edges" << endl;
	for(int i=0; i<G->sizeG; i++)
		if (G->actived_node[i]) {
			for(int j=i; j<G->sizeG; j++)
				if(G->actived_node[j] && G->E[i][j])
					cout <<"E " << i+1 << " " << j+1 << endl;
		}
	cout << "END" << endl;

	cout << endl;

	/*cout << "SECTION Cost" << endl;
	cout << "C " << G->Cost() << endl;
	cout << "END" << endl;*/
	cout << "Print Graph ////////////////////////////////////////////////////////////////////////" << endl;
}


void PrintPathMatrix(PathMatrix * PM) {

	cout << "Print Path Matrix ////////////////////////////////////////////////////////////////////////" << endl;
	for(int i=0; i<PM->sizeP; i++)
	{
		for(int j=i; j<PM->sizeP; j++)
		{
			if(!PM->P[i][j]->empty()) {
				cout << "(" << i+1 << ", " << j+1 << ")" <<endl;
				for (list<Path*>::iterator it=PM->P[i][j]->begin(); it != PM->P[i][j]->end(); ++it)
					PrintPath(*it);

				cout << endl;
			}
		}
	}
	cout << "Print Path Matrix ////////////////////////////////////////////////////////////////////////" << endl;

}

bool Uncoordinated(Graph * G_sol, PathMatrix * P_sol)
{

	for(int i=0; i<P_sol->sizeP; i++) {
		for(int j=i; j<P_sol->sizeP; j++) {
			for (list<Path*>::iterator it=P_sol->P[i][j]->begin(); it != P_sol->P[i][j]->end(); ++it)
				for (list<int>::iterator itA=(*it)->path->begin(); itA != (*it)->path->end(); ++itA) {
					if(!G_sol->actived_node[*itA]) {
						cout << "[ERROR][Uncoordinated]: Nodo no activo   "<< G_sol->actived_node[*itA] << "   " << *itA +1 << endl;
						return true;
					}
				}
		}
	}



	list<int>::iterator _itA , end;

	for(int i=0; i<P_sol->sizeP; i++) {
		for(int j=i; j<P_sol->sizeP; j++) {
			for (list<Path*>::iterator it=P_sol->P[i][j]->begin(); it != P_sol->P[i][j]->end(); ++it) {

				end = (*it)->path->end();
				end--;
				for (list<int>::iterator itA=(*it)->path->begin(); itA != end ; ++itA) {

					_itA = itA;
					_itA++;
				//	cout << "itA, _itA: " << *itA << " " << *_itA << endl;
					if(!GetMatrix(G_sol->E, *itA, *_itA)) {
						cout << "[ERROR][Uncoordinated]: Arista no activa   "<< GetMatrix(G_sol->E, *itA, *_itA) << "   (" << *itA+1 << ", " << *_itA +1<< ")"<< endl;
						return true;
					}
				}
			}
		}
	}



	return false;
}

